#include <iostream>
#include <string>
#include <map>
#include <deque>

using namespace std;

class Node {
  public:
    Node* parent;
    Node* sufRef;
    Node* out;
    char smb;
    map<char, Node*> edges;
    bool isTerm;
    Node() : parent(NULL), sufRef(NULL), out(NULL), smb(0), isTerm(false) {}
    Node(Node* prnt, char s, bool term) : parent(prnt), sufRef(NULL), out(NULL), smb(s), isTerm(term) {}
};

Node* createTrie() {
    Node* trie = new Node();
    trie->parent = trie;
    trie->sufRef = trie;

    return trie;
}

void addToTrie(const string& str, Node* trie) {
    for (size_t i = 0; i < str.size(); ++i) {
        map<char, Node*>::iterator ch = trie->edges.find(str[i]);
        if (ch != trie->edges.end()) {
            trie = ch->second;
            if (i == str.size() - 1) trie->isTerm = true;
        } else {
            Node* newNode = new Node(trie, str[i], i == (str.size() - 1));
            if (i == 0 || i == 1) newNode->sufRef = trie;
            trie->edges.insert(make_pair(str[i], newNode));
            trie = newNode;
        }
    }
}

void setSufRefs(Node* trie) {
    deque<Node*> deq;
    
    for (map<char, Node*>::iterator i = trie->edges.begin(); i != trie->edges.end(); ++i) {
        deq.push_back(i->second);
    }

    while (!deq.empty()) {
        Node* curr = deq.front();
        deq.pop_front();

        for (map<char, Node*>::iterator i = curr->edges.begin(); i != curr->edges.end(); ++i) {
            Node* parent = i->second->parent->sufRef;
            bool found = false;

            do {
                map<char, Node*>::iterator suf = parent->edges.find(i->second->smb);
                if (suf != parent->edges.end()) {
                    i->second->sufRef = suf->second;
                    if (suf->second->isTerm) i->second->out = suf->second;
                    else { i->second->out = suf->second->out; }
                    found = true;
                    break;
                } else {
                    parent = parent->sufRef;
                }
            } while (parent->sufRef != parent);

            if (!found) {
                i->second->sufRef = parent; 
            }
            deq.push_back(i->second);
        }
    }
}

void printFromNode(Node* nd) {
    string str = "";
    while (nd->sufRef != nd) {
        str += nd->smb;
        nd = nd->parent;
    }
    for (int i = str.size() - 1; i >= 0 ; --i) cout<<str[i];
    cout<<endl;
}

void getSubStrings(const string& str, Node* trie) {
    Node* tmpTrie = trie;

    for (int i = 0; i < str.size(); ++i) {
        while (tmpTrie->edges.find(str[i]) != tmpTrie->edges.end()) {
            tmpTrie = tmpTrie->edges.find(str[i])->second;
            if (tmpTrie->isTerm) {
                printFromNode(tmpTrie);
            }

            Node* outs = tmpTrie->out;

            while (outs) {
                printFromNode(outs);
                outs = outs->out;
            }

            ++i;
            if (i >= str.size()) return;
        }
        tmpTrie = tmpTrie->sufRef;
    }
}

void readString(string& str) {
    str = "";
    char c;

    scanf("%c",&c);
    while (c != '\n' && c != EOF) {
        str += c;
        scanf("%c",&c);
    }
}

void deleteTrie(Node* trie) {
    deque<Node*> deq;

    deq.push_back(trie);

    while (!deq.empty()) {
        for (map<char, Node*>::iterator i = deq.front()->edges.begin(); i != deq.front()->edges.end(); ++i) { deq.push_back(i->second); }
        delete deq.front();
        deq.pop_front();
    }

}


int main() {
    Node* trie = createTrie();

    string parts;
    cout<<"Input string parts:"<<endl;
    readString(parts);

    while (parts != "") {
        addToTrie(parts, trie);
        readString(parts);
    }

    setSufRefs(trie);

    string str;
    cout<<"Input string:"<<endl;
    readString(str);

    getSubStrings(str, trie);
    deleteTrie(trie);

    system("pause");
    return 0;
}

